1. Field of the Invention
The present invention relates to image processing, and more particularly, to block matching for determining the similarity between images.
2. Description of the Background Art
A motion vector indicative of the motion of an object appearing on each frame is obtained for example by determining the similarity between one fame and another frame of moving images. More specifically, an image area including this object is cut out from one frame, and then it is determined which image area in another frame corresponds to this image area. Such determination of the similarity between images is realized by block matching (see for example Japanese Patent Application Laid-Open No. 2006-33145).
In the block matching, similarity is determined between a target area cut out from one frame and an area (hereinafter referred to as a “comparison area”) obtained by scanning a particular area in another frame (which may be an entire area and is hereinafter referred to as a “scanning area”). Such similarity is regarded as being the similarity between the target area and the comparison area in their entirety. As a specific example, a pixel in a target area and a pixel or pixels in a comparison area are compared. Then, results of comparisons between pixels are accumulated throughout the comparison area to determine the similarity between the target area and the comparison area. As a result of the comparison between pixels, a value indicative of the difference between pixels (hereinafter referred to as a “pixel difference value”) is adopted which is for example the absolute value of the difference between values (such as brightness) of the pixels (hereinafter referred to as a “pixel difference absolute value).” The similarity discussed above is obtained as the total sum of these pixel difference values.
The above-discussed similarity is obtained for each comparison area, so a comparison area with the highest degree of similarity to a target area is found in a scanning area. Thus, a motion vector is obtained based on the position of a target area in one frame and the position of a comparison area in another frame.
In order to specify a comparison area in a scanning area that is similar to a target area, a process step for obtaining a pixel difference value should be executed a number of times corresponding to the product of the number of operations performed between one target area and one comparison area as a pair and the total sum of comparison areas obtained by scanning.
For simplification, a target area and a comparison area are regarded as being of the same size. Then, it is assumed that a pixel difference value is obtained between a pixel holding a relative position in the target area and a pixel holding this relative position in the comparison area.
If the target area is expressed as a group of pixels arranged in M rows and N columns, and a scanning area is expressed as a group of pixels arranged in J rows and K columns (where J, K, M and N are positive integers satisfying J>M and K>N), the number of comparison areas obtained in this scanning area is expressed as (J−M+1)×(K−N+1).
If pixel data corresponding to this number of comparison areas are accumulated in advance, and pixel difference values are obtained simultaneously between pixels of the pixel data of the comparison areas and corresponding pixels of the pixel data of the target area, the process step related thereto may be expedited. This however requires the storage of data of M×N pixels as the total number of pixels of the target region, and the storage of data of (J−M+1)×(K−N+1)×M×N pixels of the comparison areas. This technique disadvantageously requires a huge storage area.
This disadvantage may be overcome by one exemplary way in which pixel difference values are obtained simultaneously with respect to a plurality of comparison areas by using one pixel in a target area and respective pixels in the plurality of comparison areas corresponding to this pixel in the target area.
This case requires the storage of one pixel data relating to a target area, so when compared to the technique previously discussed, the number of pieces of pixel data to be stored is reduced to 1/(M×N). In the block matching technique, however, the similarity of images is obtained as the total sum of absolute values as discussed above. This naturally means that processing time required in this case is M×N times the processing time required in the previously discussed technique. Further, pixel data relating to a target area should be retrieved M×N times, and the retrieval of pixel data is generally accompanied by overhead. This technique thus results in longer processing time.